package com.lijing.LinkedListStack;

public class LinkedListStackDemo {
    public static void main(String[] args) {
        SingleLinkedListStack stack = new SingleLinkedListStack(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.list();

    }


}
//使用链表模拟栈，头插入，头删除，使用带头节点的单向链表


class SingleLinkedListStack{
    private int maxSize;
    private StackNode head;


    public SingleLinkedListStack(int maxSize) {
        this.maxSize = maxSize;
        head = new StackNode(-1,0);
    }

    public StackNode getHead() {
        return head;
    }

    public void setHead(StackNode head) {
        this.head = head;
    }
    //判断栈满,也就是head后面还有maxSize个节点
    public boolean isFull(){
        StackNode temp = head;
        int count = 0;
        while (temp.getNext() != null){
            count++;
            temp = temp.getNext();
        }
        if(count >= maxSize){
            return true;
        }else {
            return false;
        }
    }

    //判断栈空
    public boolean isEmpty(){
        return head.getNext() == null;
    }

    //入栈,使用头差插法
    public void push(int value){
        if(isFull()){
            System.out.println("stack is full!");
            return;
        }
        if(isEmpty()){
            head.setNext(new StackNode(1,value));
        }else{
            StackNode temp = new StackNode(head.getNext().getNo()+1,value);
            temp.setNext(head.getNext());
            head.setNext(temp);
        }

    }

    //出栈
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("stack is empty!");
        }
        int temp = head.getNext().getItem();
        System.out.println(head.getNext().getItem());
        head.setNext(head.getNext().getNext());
        return temp;
    }

    //遍历栈
    public void list(){
        if(isEmpty()){
            System.out.println("stack is empty!");
            return;
        }
        int count = head.getNext().getNo();
        StackNode temp = head.getNext();
        while(temp != null) {
            System.out.printf("stack[%d]=%d\n",temp.getNo(),temp.getItem());
            temp = temp.getNext();
        }
    }

}

class StackNode{
    private int no;
    private int item;//元素
    private StackNode next;

    public StackNode(int item) {
        this.item = item;
    }

    public StackNode(int no, int item) {
        this.no = no;
        this.item = item;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public int getItem() {
        return item;
    }

    public void setItem(int item) {
        this.item = item;
    }

    public StackNode getNext() {
        return next;
    }

    public void setNext(StackNode next) {
        this.next = next;
    }
}
